package main.java;

/**
 * @program: pratice
 * @author: 关键我是大怪
 * @create: 2021-09-09 22:17
 */

/**
 * 题目：
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * <p>
 * 示例：
 * 输入：s = "babad"
 * 输出："bab"
 * 解释："aba" 同样是符合题意的答案。
 */

public class Test18_最长回文子串 {
    public String longestPalindrome(String s) {
        int len = 0;
        int cot = 0;
        for (int i = 0; i < s.length(); i++) {
            int len1 = test(s, i, i);
            int len2 = test(s, i, i + 1);
            int max = Math.max(len1, len2);
            if (max > len) {
                len = max;
                cot = i;
            }
        }
        return s.substring(cot - (len - 1) / 2, cot + (len) / 2 + 1);
    }

    public int test(String s, int i, int j) {
        int len = 0;
        if (i == j) {
            len++;
            i--;
            j++;
        }
        while (i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)) {
            len += 2;
            i--;
            j++;
        }
        return len;
    }

    public static void main(String[] args) {
        Test18_最长回文子串 test = new Test18_最长回文子串();
        String s = test.longestPalindrome("babad");
        System.out.println(s);
    }
}
